package com.wxg.algorithm.chapter06;

public class UnionFindV5 {

    private int[] parent;
    int[] rank; // rank[i] 表示以 i 为根的集合所表示的树的层数
    private int   count;

    public UnionFindV5(int count ) {
        parent = new int[count];
        rank = new int[count];
        this.count = count;
        for ( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find( int p ) {
        if( p >= 0 && p < count) {
            while ( p != parent[p] ){
                parent[p] = parent[parent[p]];  // 就这一句, 实现路径压缩
                p = parent[p];
            }
            return p;
        }else {
            throw new RuntimeException("传入的参数不合法");
        }
    }

    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    public void union( int p , int q ) {

        int pRoot = find(p);
        int qRoot = find(q);

        if ( pRoot != qRoot ) {
            if ( rank[pRoot] < rank[qRoot] ){
                parent[pRoot] = qRoot;
            }else if ( rank[pRoot] > rank[qRoot] ){
                parent[qRoot] = pRoot;
            }else { // rank[pRoot] == rank[qRoot]
                parent[pRoot] = qRoot;
                rank[qRoot] += 1;
            }
        }
    }
}
